Search

We're now going to use another foundational AI technique to help us solve this problem: Search.

Search is used throughout AI from Game-Playing to Route Planning to efficiently find solutions.

Here's how we'll apply it. The box 'A2' has four possibilities: 1, 6, 7, and 9. Why don't we fill it in with a 1 and try to solve our puzzle. If we can't solve it, we'll try with a 6, then with a 7, and then with a 9. Sure, it's four times as much work, but each one of the cases becomes easier.

Actually, there's something a bit smarter than that. Looking carefully at the puzzle, is there a better choice for a box than 'A2'?

Choice quiz

SOLUTION:

G2

That's right - we pick G2 because it has the fewest numbers to try out.

Search

So it seems that we have a new strategy!

Strategy 3: Search

Pick a box with a minimal number of possible values. Try to solve each of the puzzles obtained by choosing each of these values, recursively.

Before we dive in to code the search function, let's first check our understanding. How would you traverse the following tree using Depth First Search?

DFS Quiz

QUESTION:

Traverse the above tree using Depth First Search.
The answer should be the string obtained by the labels in the order you've traversed the tree.
For example, if your tree has four vertices, A, B, C, D, and you've traversed them in the order B->C->A->D, then the answer should be the string 'BCAD'.

ANSWER:

SOLUTION:

NOTE: The solutions are expressed in RegEx pattern. Udacity uses these patterns to check the given answer

DFS Quiz: Solution

And here's the answer!